import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class CombinationSumII {
    /*
    * 40. 组合总和II
    * 给定一个候选人编号的集合 candidates 和一个目标数 target ，
    * 找出 candidates 中所有可以使数字和为 target 的组合。
    * candidates 中的每个数字在每个组合中只能使用 一次 。
    * 注意：解集不能包含重复的组合。
    *
    * 1 <= candidates.length <= 100
    * 1 <= candidates[i] <= 50
    * 1 <= target <= 30
    * */
    public static void main(String[] args){

    }

    // 我的想法：这就和 39.组合总和是一个道理，只是每个值只能用一次了
    // 注意审题，所给的candidates中是有重复元素的，要记得去重
    public List<List<Integer>> mySolution(int[] candidates, int target){
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    private void backtracking(int[] candidates, int target, int start){
        if(target < 0) return;
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length && candidates[i] <= target; i++) {
            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i+1);    // 不可重复，所以得+1
            path.pollLast();
            // 去重，一定要在递归末尾去重，这样既能保证含有相同数字的组合不会被忽略，又不会添加重复组合
            // 因为用过的元素不能重复，你得先用，再判断重复
            while (i+1<candidates.length && candidates[i] == candidates[i+1])
                i++;
        }
    }
}
